Theory of Computation
Table of Contents
1. Turing Machine
A stateful read-write operator and an modifiable infinite strip of zeroes and ones.
Turing proves that this machine can do anything that a computer can do. Inversely, a machine that can do anything that Turing machine can do is called Turing-complete.
2. Quine
A code that prints itself.
3. Halting Problem
Does a program that tells whether the program will halt exists?
The code that passes itself to such program and negates the output result in contradiction, denying the existence.
4. Minimal Problem
Does program that tells whether a code is minimal, that is, there is no shorter code that outputs the same, exists?
Let us assume such program \( M \) exists. A program that generates codes longer than its own length and pass it to \( M \) until minimal program is found, then simulate the minimal program, is a shorter code then the alleged minimal program. Therefore \( M \) cannot exists.